//
//  98_验证二叉搜索树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/13.
/*
 https://leetcode.cn/problems/validate-binary-search-tree/
 */

import UIKit

class IsBST: NSObject {
    
    func QA() {
        let tree = BinaryTree<Int>()
        let root = tree.creatBinaryTree([5,4,6,-1,-1,3,7])
        BinaryTree.printBinaryTree(root)
        print(isValidBST(root))
    }
    
    func isValidBST(_ root: TreeNode<Int>?) -> Bool {
        
       
        return isNodeBST(root, minNum: Int.min, maxNum: Int.max)
    }
    
    /// 判断节点在min和max之间
    /// - Parameters:
    ///   - node: 节点
    ///   - minNum: 较小
    ///   - maxNum: 较大
    /// - Returns: 结果
    func isNodeBST(_ node: TreeNode<Int>?, minNum: Int, maxNum: Int) -> Bool {
        guard let node = node else {
            return true
        }
        if node.val <= minNum || node.val >= maxNum {
            return false
        }
        // 左边的节点都小于自己，右边的都大于自己
        return isNodeBST(node.left, minNum: minNum, maxNum: node.val) && isNodeBST(node.right, minNum: node.val, maxNum: maxNum)
    }
}
